def convex_hull(points):
    """
    计算一组二维点的凸包。

    输入: 一个可迭代的序列，包含表示点的 (x, y) 元组。
    输出: 一个列表，包含凸包的顶点，按逆时针顺序排列，从字典序最小的坐标的顶点开始。
    实现了 Andrew 的单调链算法，时间复杂度为 O(n log n)。
    """

    # Sort the points lexicographically (tuples are compared lexicographically).
    # Remove duplicates to detect the case we have just one unique point.
    # 按字典序对这些点进行排序（元组会按字典序比较）
    # 移除重复的点，以处理只有一个唯一点的情况
    points = sorted(set(points))

    # Boring case: no points or a single point, possibly repeated multiple times.
    # 简单情况：没有点或者只有一个点（可能重复多次）
    if len(points) <= 1:
        return points

    # 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
    # Returns a positive value, if OAB makes a counter-clockwise turn,
    # negative for clockwise turn, and zero if the points are collinear.
    def cross(o, a, b):
        """
        计算二维向量 OA 和 OB 的叉积，即它们在三维空间中叉积的 z 分量。
        如果 OAB 构成逆时针旋转，则返回正值；
        如果是顺时针旋转，则返回负值；
        如果三点共线，则返回零。

        :param o: 原点 (x, y)
        :param a: 第一个点 (x, y)
        :param b: 第二个点 (x, y)
        :return: 叉积结果
        """
        return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

    # Build lower hull
    # 构建下凸包
    lower = []
    for p in points:
        # 当 lower 列表中至少有两个点，并且当前点与 lower 列表中最后两个点构成顺时针或共线时
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            # 移除 lower 列表中的最后一个点
            lower.pop()
        # 将当前点添加到 lower 列表中
        lower.append(p)

    # Build upper hull
    # 构建上凸包
    upper = []
    for p in reversed(points):
        # 当 upper 列表中至少有两个点，并且当前点与 upper 列表中最后两个点构成顺时针或共线时
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            # 移除 upper 列表中的最后一个点
            upper.pop()
        # 将当前点添加到 upper 列表中
        upper.append(p)

    # Concatenation of the lower and upper hulls gives the convex hull.
    # Last point of each list is omitted because it is repeated at the beginning of the other list.
    # 下凸包和上凸包的连接即为最终的凸包
    # 每个列表的最后一个点会被省略，因为它会在另一个列表的开头重复出现
    return lower[:-1] + upper[:-1]